﻿/*
题目: 最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

https://leetcode.cn/problems/longest-duplicate-substring/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    /**
    * 1. 二分查找，如果 len = n 不存在重复字串，如果存在 n 的重复子串，那么一定存在 < n 的重复子串
    * 2. 自定义哈希，转正 D 进制的整数，并减少哈希碰撞
    * 3. 为了降低哈希冲突，使用两个 哈希 函数来完成相等的判断
    */

    constexpr static int P1 = 7;
    constexpr static int P2 = 5;


    // 最长长度的重复子串
    string longestDupSubstring(string s) {
        string res;

        int left = 0, right = s.size() - 1;
        while (left <= right) {
            // +1 即向上取整
            int guess_len = left + ((right - left + 1) >> 1);
            string search = find(s, guess_len);

            if (search.size() == 0) {       // 没找到
                right = guess_len - 1;
            }
            else {                          // 找到了
                left = guess_len + 1;
            }

            if (search.size() > res.size())  res = search;
        }

        return res;
    }

    using ULL = unsigned long long;
    using PULL = pair<ULL, ULL>;
    string find(const string& s, int len) {
        // 通过滑动窗口的方式来计算所有子串的 哈希值，ULL 会自动帮我们取模
        ULL hash1 = 0, hash2 = 0;
        ULL mp1 = 1, mp2 = 1;       // 当前 len 的最大进制，用于窗口右移的删减

        set<PULL> vis;
        for (int i = 0; i < len; i++) {
            hash1 = (hash1 * P1) + s[i];
            hash2 = (hash2 * P2) + s[i];

            mp1 *= P1;
            mp2 *= P2;
        }
        vis.insert({ hash1, hash2 });

        for (int i = len; i < s.size(); i++) {
            hash1 = (hash1 * P1 + s[i]) - mp1 * s[i - len];
            hash2 = (hash2 * P2 + s[i]) - mp2 * s[i - len];

            if (vis.count({ hash1, hash2 })) {
                return s.substr(i - len + 1, len);
            }
            vis.insert({ hash1, hash2 });
        }

        return "";
    }
};
